package leetcode;

import java.util.*;

public class Demo {


    // 30. 串联所有单词的子串
    public static List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> map1 = new HashMap<>();     // 记录 words 中每个单词出现的次数
        for (String word : words) map1.put(word, map1.getOrDefault(word, 0) + 1);
        char[] array = s.toCharArray();
        int n = words[0].length();
        List<Integer> ret = new ArrayList<>();

        for(int i = 0; i < n; i++) {        // 执行次数
            Map<String, Integer> map2 = new HashMap<>();     // 保存窗口内所有子串出现的次数
            for(int left = i, right = i, count = 0; right + n <= array.length; right += n) {
                String in = new String(array, right, n);
                map2.put(in, map2.getOrDefault(in, 0) + 1);   // 进窗口
                if(map2.get(in) <= map1.getOrDefault(in, 0)) count++;  // 维护count
                // 判断是否出窗口
                if(right - left + 1 > n * words.length) {
                    String out = new String(array, left, n);
                    if(map1.get(out) != null && map2.get(out) <= map1.get(out)) count--;    // 维护count
                    map2.put(out, map2.get(out) - 1);           // 出窗口
                    left += n;
                }
                // 更新结果
                if(count == words.length) ret.add(left);

            }
        }
        return ret;
    }


    //704. 二分查找
    public int search(int[] nums, int target) {
        int mid = -1;;
        for(int left = 0, right = nums.length - 1; left <= right;) {
            mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }


    //34. 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(nums.length == 0) return ret;
        int left = 0, right = nums.length - 1, mid = -1;
        // 寻找左端点
        while (left < right) {
            mid = left + (right - left) / 2;    // 防溢出，且定位到中间元素的左边那个
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] == target) ret[0] = right;
        // 寻找右端点
        for(left = 0, right = nums.length - 1; left < right; ) {
            mid = left + (right - left + 1) / 2;    // 防溢出，且定位到中间元素的右边那个
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        if(nums[left] == target) ret[1] = left;
        return ret;
    }


    //69. x 的平方根
    public int mySqrt(int x) {
        if(x == 0) return 0;
        long left = 1, right = x, mid = 0;
        while (left < right) {
            mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return (int)left;
    }



    //35. 搜索插入位置
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length- 1, mid;
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        if(nums[left] < target) return left + 1;
        return left;
    }


    //852. 山脉数组的峰顶索引
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1, mid;
        while(left < right) {
            mid = (left + right) / 2;
            if(arr[mid] >= arr[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }


    //162. 寻找峰值
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }



    //153. 寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left + 1) / 2;
            if(nums[mid] < nums[left] && nums[mid] <= nums[right]) right = mid - 1;
            else left = mid;
        }
        if(left == nums.length - 1) return nums[0];
        return nums[left + 1];
    }


    //1518. 换水问题
    public int numWaterBottles(int numBottles, int numExchange) {
        int ret = numBottles, currentBottles = numBottles;
        while(currentBottles >= numExchange) {
            int newBottle = currentBottles / numExchange;
            ret += newBottle;
            currentBottles = newBottle + currentBottles % numExchange;
        }
        return ret;
    }


    //LCR 012. 寻找数组的中心下标
    public int pivotIndex(int[] nums) {
        // 计算 下标为0 ~ i 的前缀和,f[i]表示 0 ~ i-1项的和
        int[] f = new int[nums.length];
        f[0] = 0;
        for(int i = 1; i < f.length; i++)
            f[i] = f[i - 1] + nums[i - 1];
        // 计数0 ~ i 的后缀和, g[i]表示 下标i+1到nums.length-1的元素和
        int[] g = new int[nums.length];
        g[nums.length - 1] = 0;
        for(int i = nums.length - 2; i >= 0; i--)
            g[i] = g[i + 1] + nums[i + 1];
        for(int i = 0; i < nums.length; i++) {
            if(f[i] == g[i]) return i;
        }
        return -1;
    }


    //238. 除自身以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int[] f = new int[nums.length];
        int[] g = new int[nums.length];
        f[0] = 1; g[nums.length - 1] = 1;
        // 计数前 i 项元素的积
        for(int i = 1; i < nums.length; i++)
            f[i] = f[i-1] * nums[i-1];
        // 计算后 i 项元素的积
        for(int i = nums.length - 2; i >= 0; i--)
            g[i] = g[i+1] * nums[i+1];
        // 利用前缀积和后缀积 计算结果
        int[] ret = new int[nums.length];
        for(int i = 0; i < nums.length; i++) ret[i] = f[i] * g[i];
        return ret;
    }


    //2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int extra = 0;
        ListNode head = new ListNode();
        ListNode tail = head;
        while(l1 != null || l2 != null) {
            int value = extra;
            if(l1 != null) {
                value += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                value += l2.val;
                l2 = l2.next;
            }
            ListNode node = new ListNode(value % 10);
            extra = value / 10;
            tail.next = node; tail = node;
        }
        if(extra != 0) tail.next = new ListNode(extra);
        return head.next;

    }



    // LCR 010. 和为 K 的子数组
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();   //key记录每个下标的前缀和，value记录前缀和出现的次数
        hash.put(0,1);      // 防止0 ~ i 位置的和为k

        int sum = 0, ret = 0;
        for(int x : nums) {
            sum += x;
            ret += hash.getOrDefault(sum-k,0);       // 统计结果
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }


    //974. 和可被 K 整除的子数组
    public int subarraysDivByK(int[] nums, int k) {
        // key存放每个下标前缀和 % k的值， value存放各个余数出现的次数
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0, 1);     // 防止下标 0 ~ i的元素和 % k == 0

        int sum = 0, ret = 0;
        for(int x : nums) {
            sum += x;
            int rest = (sum % k + k) % k;   //记录余数
            ret += hash.getOrDefault(rest,0);
            hash.put(rest,hash.getOrDefault(rest,0) + 1);
        }
        return ret;
    }


    //LCR 011. 连续数组
    public int findMaxLength(int[] nums) {
        // key记录前缀和，value记录当前前缀和的下标
        Map<Integer, Integer> hash = new HashMap<>();
        int sum = 0, ret = 0;
        hash.put(0,-1);

        for(int i = 0; i < nums.length; i++) {
            sum += nums[i]==1?1:-1;
            if(hash.get(sum) != null) ret = Math.max(ret, i - hash.get(sum));
            if(!hash.containsKey(sum)) hash.put(sum,i); // 前缀和相同时，只保存前面前缀和的下标
        }
        return ret;
    }



    //338. 比特位计数
    public int[] countBits(int n) {
        int[] ret = new int[n+1];
        for(int i = 0; i <= n; i++) {
            int k = i;
            int count = 0;
            while(k > 0) {
                count++;
                k = k & (k-1);
            }
            ret[i] = count;
        }
        return ret;
    }
}
